#include<iostream>
#include<time.h>
#include<stdlib.h>
#include<vector>
using namespace std;
void UpJust(vector<int>& arr,int child)
{
    int parent=(child-1)/2;
    while(parent>=0)
    {
        if(arr[child]>=arr[parent])
        {
            swap(arr[child],arr[parent]);
            child=parent;
            parent=(child-1)/2;
        }
        else break;
    }
}
void DownJust(vector<int>& arr,int parent,int sz)
{
    int child=parent*2+1;
    while(child<sz)
    {
        if(child+1<sz&&arr[child+1]>arr[child])
            child++;
        if(arr[child]>arr[parent])
        {
            swap(arr[child],arr[parent]);
            parent=child;
            child=parent*2+1;
        }
        else break;
    }
}
void Sort(vector<int>& arr)
{
    int n=arr.size();
    for(int i=(n-1-1)/2;i>=0;i--)
        DownJust(arr,i,n);
    int p=n;
    while(p>0)
    {
        swap(arr[--p],arr[0]);
        DownJust(arr,0,p);
    }
}    
int main()
{
    srand((unsigned int)time(nullptr));
    const int n=10;
    vector<int> arr(n);
    int k=10;
    while(k--)
    {
        for(int i=0;i<n;i++)
        {
            arr[i]=rand()%100+1;
            cout<<arr[i]<<' ';
        }
        cout<<endl;
        Sort(arr);
        for(auto val:arr) cout<<val<<' ';
        cout<<endl<<endl;
    }
    return 0;
}
